package recursion

func ConvertLetterStr(str string) int {
	return ConvertProcess(str, 0)
}

func ConvertProcess(str string, index int) int {
	if index == len(str) {
		return 1
	}
	if index > len(str) {
		return -1
	}
	if str[index] == '0' {
		return -1
	}

	if str[index] == '1' {
		res := 0
		p1 := ConvertProcess(str, index+1)
		p2 := ConvertProcess(str, index+2)
		if p1 != -1 {
			res += p1
		}
		if p2 != -1 {
			res += p2
		}
		return res
	}

	if str[index] == '2' {
		res := 0
		p1 := -1
		p2 := -1
		p1 = ConvertProcess(str, index+1)
		if str[index] >= '0' && str[index] <= '6' && index+1 < len(str)  {
			p2 = ConvertProcess(str, index+2)
		}
		if p1 != -1 {
			res += p1
		}
		if p2 != -1 {
			res += p2
		}
		return res
	}

	return ConvertProcess(str, index+1)
}

func ConvertLetterStr2(str string) int {
	return ConvertProcess2(str, 0)
}

func ConvertProcess2(str string, index int) int {
	if index == len(str) {
		return 1
	}
	if str[index] == '0' {
		return 0
	}
	if str[index] == '1' {
		res := ConvertProcess2(str, index+1)
		if index+1 < len(str) {
			res += ConvertProcess2(str, index+2)
		}
		return res
	}

	if str[index] == '2' {
		res := ConvertProcess2(str, index+1)
		if index+1 <= len(str) && str[index] >= '0' && str[index] <= '6' {
			res += ConvertProcess2(str, index+2)
		}
		return res
	}

	return ConvertProcess2(str, index+1)
}

func ConvertLetterStrDp(str string) int {
	ans := make([]int, len(str)+1)
	ans[len(str)] = 1

	for i:=len(str)-1; i>=0; i-- {
		if str[i] == '0' {
			ans[i] = 0
		}
		if str[i] == '1' {
			ans[i] = ans[i+1]
			if i+1 < len(str) {
				ans[i] = ans[i+2] + ans[i]
			}
		}
		if str[i] == '2' {
			ans[i] = ans[i+1]
			if i+1 < len(str) && str[i] >= '0' && str[i] <= '6' {
				ans[i] = ans[i+2] + ans[i]
			}
		}
	}
	return ans[0]
}
